package codeRandomThoughts.Test518零钱兑换II;

public class Solution {
    public int change(int amount, int[] coins) {
        //用编号0-i的coin凑成总金额为j的硬币组合数有dp[j]种
        int[] dp = new int[amount + 1];

        //初始化dp
        dp[0] = 1;//凑成总金额为0的硬币组合数有1种,就是什么也不放

        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                //两种情况
                //1.不考虑coins[i]
                //dp[j] = (i-1) dp[j]
                //2.考虑coins[i]
                //dp[j] = (i) dp[j - coins[i]]
                dp[j] += dp[j - coins[i]];
            }
        }

        return dp[amount];
    }
}
